package com.cn.algorithm02.class14;

import com.cn.algorithm02.class01.Nodea;

/***
 * @author: hels
 * @description: 通过递归的方式判断是否为完全二叉树
 **/
public class C01_IsCBT2 {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        Nodea head = Nodea.getNodeInstance(arr);
        //head.right.left = new Nodea(5);

        Nodea.printTree(head);
        System.out.println(isCBT(head));
    }

    public static boolean isCBT(Nodea head) {
        if (head == null) return true;
        return process(head).isCBT;
    }

    public static Info process(Nodea x) {
        if (x == null) return new Info(true, true, 0);
        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);

        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        boolean isFBT = leftInfo.isFBT && rightInfo.isFBT && leftInfo.height == rightInfo.height;


        boolean isCBT = isFBT;
        /*if (leftInfo.isFBT && rightInfo.isFBT && leftInfo.height == rightInfo.height) {
            isCBT = true;
        }*/
        if (leftInfo.isCBT && rightInfo.isFBT && leftInfo.height == rightInfo.height + 1) {
            isCBT = true;
        }else if (leftInfo.isFBT && rightInfo.isFBT && leftInfo.height == rightInfo.height + 1) {
            isCBT = true;
        }else if (leftInfo.isFBT && rightInfo.isCBT && leftInfo.height == rightInfo.height) {
            isCBT = true;
        }


        return new Info(isFBT, isCBT, height);
    }

    public static class Info {
        public boolean isFBT;
        public boolean isCBT;
        public int height;

        public Info(boolean isFBT, boolean isCBT, int height) {
            this.isFBT = isFBT;
            this.isCBT = isCBT;
            this.height = height;
        }
    }
}
